1. Technical Field
The present invention relates in general to a method and system for displaying information and in particular to a method and system for displaying system operation trace information. Still more particularly, the present invention relates to a method and system for graphically displaying system operation trace information so that graphical objects representing event-pairs within the system operation are not visually obscured.
2. Description of the Related Art
A "trace" of a software or a hardware system is a recording of the chronology of events or states which the system executes. Trace chronologies are used in performance analysis and debugging. Events in trace chronologies are often paired, forming event-pairs. Examples of events which are paired in this way are the start and end times of programs, functions, and system calls.
Event-pairs within a trace may be nested. Event-pair A is synchronously nested under event-pair B if A begins and ends within B's execution. That is, A is synchronously nested under B if STARTTIME (A)&gt;STARTTIME (B) and ENDTIME (A)&lt;ENDTIME (B). In such a case, one may refer to B as the a synchronous "ancestor" of A, and A as a synchronous "descendant" of B. An example of a synchronously nested event-pair is a system call which executes entirely within a function. Event-pairs may also be asynchronously nested. For event-pair A to be asynchronously nested under B, it is necessary and sufficient that A begins within the execution of B and all of B's ancestors, and that A ends after B ends. That is, A is asynchronously nested under B when STARTTIME (A)&gt;STARTTIME (B and all of B's ancestors) and ENDTIME (A)&gt;ENDTIME (B). In such a case, one may refer to B as an asynchronous "ancestor" of A, and A as an asynchronous "descendant" of B. An example of an asynchronously nested event-pair is a page-fault which causes I/O to begin within a system call.
Trace chronologies are more effectively utilized when event-pairs are displayed graphically along a time line. A Ghant chart, also known as a bar chart or a histogram, is a common format for displaying trace chronologies. In a Ghant chart, rectangles of various lengths, representing different event-pairs, are arranged parallel to a time axis. State-of-the-art trace visualization tools like PieScope, a tool developed by IBM Corp., permit event-pair nesting and represent nested event-pairs by displaying adjacent or overlapping rectangles in a complex Ghant chart.
A drawing problem arises, however, when two unrelated and mutually unnested event-pairs (event-pairs not nested with each other) are assigned equal nesting depths and at least one of them is asynchronously nested with a third event-pair. For example, assume A1, A2, B1 and B2 are event-pairs. Assume B1 is synchronously nested under A1 and B2 is synchronously nested under A2. Assume, also, that A1 and B1 are mutually unnested with A2 and B2. If A1 and A2 have nesting levels of zero and B1 and B2 have nesting levels of one, a graphical object representing event-pair B1 will partly or completely obscure a graphical object representing B2 if ENDTIME (B1)&gt;STARTTIME (B2). Consequently, it would be desirable to have a method and system for graphically displaying trace chronologies in which asynchronously nested event-pairs are represented without obscuring graphical objects representing other event-pairs.
An additional problem arises in storing the data required to graphically display event-pairs within a trace chronology. Event-pair data are often stored in data structures having a number of entries representing event-pairs within the trace chronology. Each entry includes pointers or other indicia of the relationship of its event-pair to other event-pairs within the trace chronology. To insert an event-pair in the trace chronology, an algorithm is utilized to determine the relationship of a new event-pair to existing event-pairs and to reflect the relationship by inserting an entry storing data utilized to display the new event-pair at the proper location in the data structure.
Algorithms utilized in state-of-the-art trace visualization tools such as PieScope, which enable the depiction of asynchronous event-pairs, are often cumbersome and inefficient because they utilize many tests to determine relationships between event-pairs. For example, earlier version of PieScope utilize an algorithm which determines the insertion point by comparing the start and end times of the new event pair to the start and end times of each successive event-pair within the data structure, beginning with the earliest occurring event-pair. Earlier versions of the PieScope algorithm also utilize a multiplicity of comparisons to determine how the insertion of the new event-pair affects the relationships of surrounding event-pairs. Consequently, it would be desirable to have a method and system for efficiently inserting event-pairs in a data structure storing data utilized to display a trace chronology.